package com.java.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 希尔排序
 *
 * @author 19252
 * @date 2020/7/17
 */
public class ShellSort {

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] array = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 0};
        // int[] array = new int[]{10, 2};
//        shellSort.sortBySwap(array);
//        shellSort.sortByMove(array);
//        for (int value : array) {
//            System.out.print(value + " ");
//        }

        // 效率测试
        Random random = new Random();
        int[] testArray = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            testArray[i] = random.nextInt(8000000);
        }
        long millis = System.currentTimeMillis();
        // shellSort.sortBySwap(testArray);
        shellSort.sortByMove(testArray);
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");
    }

    /**
     * 希尔排序,交换法
     *
     * @param array 传入的数组
     */
    public void sortBySwap(int[] array) {
        int length = array.length;
        // 对数组的长度除2 获得初始分组
        int divideNum = 2;
        // group 是表示该数组在此次分组中分为几组，group 即同组元素之间相距的步长
        int group = length / divideNum;
        // 辅助变量保存值
        int temp;
        // 辅助变量保存索引
        int index;
        // 最外层循环控制分组次数
        for (int i = group; i > 0; i /= divideNum) {
            // 对不同分组进行插入排序
            for (int j = 0; j < i; j++) {
                // 对分组进行插入排序，从分组的第二个元素开始，元素的是否在同一分组是根据步长来判断的
                for (int k = j + i; k < length; k = k + i) {
                    // 保存索引
                    index = k;
                    // 根据步长来控制分组的排序成员
                    while (index >= i && (array[index - i] > array[index])) {
                        // 条件达成，数据交换
                        temp = array[index];
                        array[index] = array[index - i];
                        array[index - i] = temp;
                        // 此时数据向前移动一个步长，在进行数据比较
                        index -= i;
                    }
                    // 当该分组的前一部分完成排序
                    // 索引 k 正常增加一个步长到达下一个分组元素
                }

            }
            // System.out.println(i + Arrays.toString(array));
        }
    }


    /**
     * 希尔排序，移位法
     *
     * @param array
     */
    public void sortByMove(int[] array) {
        int length = array.length;
        // 对数组的长度除2 获得初始分组
        int divideNum = 2;
        // group 是表示该数组在此次分组中分为几组，group 即同组元素之间相距的步长
        int group = length / divideNum;
        // 辅助变量保存值
        int temp;
        // 辅助变量保存索引
        int index;
        for (int i = group; i > 0; i /= divideNum) {
            for (int j = 0; j < i; j++) {
                for (int k = j + i; k < length; k += i) {
                    temp = array[k];
                    index = k;
                    // 移动数据，而不是交换
                    while (index >= i && (array[index - i] > temp)) {
                        array[index] = array[index - i];
                        index -= i;
                    }
                    array[index] = temp;
                }
            }
        }
    }
}
